home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ddj0897.zip / DYN401.ZIP / class / set.d < prev    next >
Text File  |  1996-08-25  |  11KB  |  558 lines
  1.  
  2.  
  3. /*                                      
  4.  *
  5.  *      Copyright (c) 1993-1996 Algorithms Corporation
  6.  *      3020 Liberty Hills Drive
  7.  *      Franklin, TN 37067
  8.  *
  9.  *      ALL RIGHTS RESERVED.
  10.  *
  11.  *      
  12.  *      
  13.  */
  14.  
  15.  
  16. #include <string.h>
  17. #include <math.h>
  18.  
  19. #include "set1.h"
  20.  
  21.  
  22. defclass  Set  {
  23.     int    iSize;        /*  size of iTab        */
  24.     int    iNelm;        /*  number of entries in iTab    */
  25.     NODE    *iTab;        /*  the hash table        */
  26.     CRITICALSECTION    iCS;    /*  in support of native threads  */
  27. class:
  28.     NODE    FNODES;        /*  free node structures    */
  29.     CRITICALSECTION    cCS;    /*  in support of native threads  */
  30.  init:    class_init;
  31. };
  32.  
  33.  
  34.  
  35. static    objrtn    Lookup(object self, object luk, int mode, int deep, int type, object value);
  36.  
  37. #define LTYPE    0    /*  lookup type        */
  38.  
  39. #define NODE_BLOCK_SIZE        50
  40.  
  41. static    NODE    new_node(void)
  42. {
  43.     int    i;
  44.     volatile  NODE    r;
  45.  
  46.     ENTERCRITICALSECTION(cCS);
  47.     if (!FNODES)  {
  48.         FNODES = Tncalloc(struct NODES, NODE_BLOCK_SIZE);
  49.         for (i=0 ; i != (NODE_BLOCK_SIZE-1) ; ++i)
  50.             FNODES[i].next = FNODES + (i + 1);
  51.         gRegisterMemory(Dynace, FNODES, (long)(sizeof(struct NODES) * NODE_BLOCK_SIZE));
  52.     }
  53.     r = FNODES;
  54.     FNODES = FNODES->next;
  55.     LEAVECRITICALSECTION(cCS);
  56.     return r;
  57. }
  58.  
  59. static    void    free_node(NODE i)
  60. {
  61.     ENTERCRITICALSECTION(cCS);
  62.     i->luk = NULL;
  63.     i->next = FNODES;
  64.     FNODES = i;
  65.     LEAVECRITICALSECTION(cCS);
  66. }
  67.  
  68. cmeth    gNewWithInt, <vNew> : New (int size)
  69. {
  70.     object    set = gNew(super);
  71.     ivType    *iv = ivPtr(set);
  72.     iSize = size;
  73.     iTab = Tncalloc(NODE, size);
  74.     INITIALIZECRITICALSECTION(iCS);
  75.     return set;
  76. }
  77.  
  78. cmeth    gNew()
  79. {
  80.     return New(self, 51);
  81. }
  82.  
  83. private    imeth    _copy(object self, int deep)
  84. {
  85.     object    nobj;
  86.     ivType    *iv2;
  87.     int    i;
  88.  
  89.     ENTERCRITICALSECTION(iCS);
  90.     if (deep < 2)
  91.         nobj = gCopy(super);
  92.     else
  93.         nobj = gDeepCopy(super);
  94.     iv2 = ivPtr(nobj);
  95.  
  96.     iv2->iSize = iSize;
  97.     iv2->iTab = Tncalloc(NODE, iv2->iSize);
  98.     for (i=0 ; i != iv2->iSize ; ++i)  {
  99.         NODE    n, n2, p;
  100.  
  101.         for (n=iTab[i], p=NULL ; n ; p=n2, n=n->next)  {
  102.             n2 = new_node();
  103.             switch (deep)  {
  104.             case 0:
  105.             default:
  106.                 n2->luk = n->luk;
  107.                 break;
  108.             case 1:
  109.                 n2->luk = gCopy(n->luk);
  110.                 break;
  111.             case 2:
  112.                 n2->luk = gDeepCopy(n->luk);
  113.                 break;
  114.             }
  115.             n2->next = NULL;
  116.             if (p)
  117.                 p->next = n2;
  118.             else
  119.                 iv2->iTab[i] = n2;
  120.         }
  121.     }
  122.     LEAVECRITICALSECTION(iCS);
  123.     return nobj;
  124. }
  125.  
  126. imeth    gCopy()
  127. {
  128.     return _copy(self, ClassOf(self) != CLASS);
  129. }
  130.  
  131. imeth    gDeepCopy()
  132. {
  133.     return _copy(self, 2);
  134. }
  135.  
  136.  
  137.  
  138. /* returns the number of elements in the hash table    */
  139.  
  140. imeth    int    gSize()
  141. {
  142.     return iNelm;
  143. }
  144.  
  145. private    imeth    object    _delete(object self, int mode, int entire)
  146. {
  147.     int    i;
  148.     
  149.     ENTERCRITICALSECTION(iCS);
  150.     for (i=0 ; i != iSize ; ++i)  {
  151.         NODE    n, p = iTab[i];
  152.         
  153.         for (; p ; p = n)  {
  154.             if (mode == 1)
  155.                 gDispose(p->luk);
  156.             else if (mode == 2)
  157.                 gDeepDispose(p->luk);
  158.             n = p->next;
  159.             free_node(p);
  160.         }
  161.         iTab[i] = NULL;
  162.     }
  163.     if (entire)  {
  164.         free(iTab);
  165.         LEAVECRITICALSECTION(iCS);
  166.         DELETECRITICALSECTION(iCS);
  167.         self = gDispose(super);
  168.     } else {
  169.         iNelm = 0;
  170.         LEAVECRITICALSECTION(iCS);
  171.     }
  172.     return self;
  173. }    
  174.  
  175. imeth    object    gDispose, gGCDispose ()
  176. {
  177.     return _delete(self, 0, 1);
  178. }
  179.  
  180. imeth    object    gDeepDispose()
  181. {
  182.     return _delete(self, 2, 1);
  183. }
  184.  
  185. imeth    object    gDispose1()
  186. {
  187.     return _delete(self, 1, 1);
  188. }
  189.  
  190. imeth    object    gDisposeAllNodes()
  191. {
  192.     return _delete(self, 0, 0);
  193. }
  194.  
  195. imeth    object    gDeepDisposeAllNodes()
  196. {
  197.     return _delete(self, 2, 0);
  198. }
  199.  
  200. imeth    object    gDisposeAllNodes1()
  201. {
  202.     return _delete(self, 1, 0);
  203. }
  204.  
  205. /*  execute fun for every key in the table until fun returns non-NULL    */
  206.  
  207. imeth    gForAll(object (*fun) (/* ??? */))
  208. {
  209.     int    i;
  210.     
  211.     ENTERCRITICALSECTION(iCS);
  212.     for (i=0 ; i != iSize ; ++i)  {
  213.         NODE    p = iTab[i];
  214.         object    v;
  215.         
  216.         for (; p ; p = p->next)
  217.             if (v = (*(object (*)(object))fun)(p->luk)) {
  218.                 LEAVECRITICALSECTION(iCS);
  219.                 return(v);
  220.             }
  221.     }
  222.     LEAVECRITICALSECTION(iCS);
  223.     return NULL;
  224. }
  225.  
  226. imeth    gStringRep()
  227. {
  228.     int    i;
  229.     object    s, t;
  230.     
  231.     s = gStringRepValue(super);
  232.     gAppend(s, (object) "  [\n");
  233.     for (i=0 ; i != iSize  &&  !iTab[i] ; ++i);
  234.     while (i != iSize)  {
  235.         NODE    p = iTab[i];
  236.         
  237.         while (++i != iSize  &&  !iTab[i]);
  238.         while (p)  {
  239.             t = gStringRepValue(p->luk);
  240.             if ((p = p->next)  ||  i != iSize)
  241.                 vBuild(s, NULL, "\t", t, ",\n", NULL);
  242.             else
  243.                 vBuild(s, NULL, "\t", t, "\n", NULL);
  244.             gDispose(t);
  245.         }
  246.     }
  247.     gAppend(s, (object) "]\n");
  248.     return s;
  249. }
  250.  
  251. /*  add a new luk if it doesnt already exist - 
  252.     return NULL if it previously existed
  253.    */
  254.  
  255. imeth    gAdd, <vAdd> (luk)
  256. {
  257.     ChkArg(luk, 2);
  258.     return Lookup(self, luk, HT_ADD, 0, LTYPE, NULL);
  259. }
  260.  
  261. /*  find an existing key  (return NULL if can't find)    */
  262.  
  263. imeth    gFind, <vFind> (luk)
  264. {
  265.     ChkArg(luk, 2);
  266.     return Lookup(self, luk, HT_FIND, 0, LTYPE, NULL);
  267. }
  268.  
  269. /* find a key - if doesn't exist add  */
  270.  
  271. imeth    gFindAdd, <vFindAdd> (luk)
  272. {
  273.     ChkArg(luk, 2);
  274.     return Lookup(self, luk, HT_FINDADD, 0, LTYPE, NULL);
  275. }
  276.  
  277. /*  dispose of a node - if it doesnt exist return NULL  */
  278.  
  279. imeth    gRemoveObj, <vRemove> (luk)
  280. {
  281.     ChkArg(luk, 2);
  282.     return Lookup(self, luk, HT_DELETE, 0, LTYPE, NULL);
  283. }
  284.  
  285. /*  dispose of a node - if it doesnt exist return NULL  */
  286.  
  287. imeth    gDisposeObj(luk)
  288. {
  289.     ChkArg(luk, 2);
  290.     return Lookup(self, luk, HT_DELETE, 1, LTYPE, NULL);
  291. }
  292.  
  293. /*  deep dispose of a node - if it doesnt exist return NULL  */
  294.  
  295. imeth    gDeepDisposeObj(luk)
  296. {
  297.     ChkArg(luk, 2);
  298.     return Lookup(self, luk, HT_DELETE, 2, LTYPE, NULL);
  299. }
  300.  
  301. /* dispose of a group of entries    */
  302.  
  303. private    imeth    _deleteGroup(object self, int (*fun) (/* ??? */), int deep)
  304. {
  305.     int    i;
  306.     NODE    n, lastp, p;
  307.     
  308.     ENTERCRITICALSECTION(iCS);
  309.     for (i=0 ; i != iSize ; ++i)  {
  310.         for (lastp=NULL, p=iTab[i] ; p ; )
  311.             if ((*(int (*)(object))fun)(p->luk))  {
  312.                 if (deep == 1)
  313.                     gDispose(p->luk);
  314.                 else if (deep == 2)
  315.                     gDeepDispose(p->luk);
  316.                 if (lastp)
  317.                     lastp->next = n = p->next;
  318.                 else
  319.                     iTab[i] = n = p->next;
  320.                 free_node(p);
  321.                 p = n;
  322.                 --iNelm;
  323.             }  else  {
  324.                 lastp = p;
  325.                 p = p->next;
  326.             }
  327.     }
  328.     LEAVECRITICALSECTION(iCS);
  329.     return self;
  330. }
  331.  
  332. imeth    gGroupRemove(int (*fun) (/* ??? */))
  333. {
  334.     return _deleteGroup(self, fun, 0);
  335. }
  336.  
  337. imeth    gDisposeGroup(int (*fun) (/* ??? */))
  338. {
  339.     return _deleteGroup(self, fun, 1);
  340. }
  341.  
  342. imeth    gDeepDisposeGroup(int (*fun) (/* ??? */))
  343. {
  344.     return _deleteGroup(self, fun, 2);
  345. }
  346.  
  347.  
  348. /*  change the size of a hash table    */
  349.  
  350. imeth    gResize(int size)
  351. {
  352.     NODE    *v;
  353.     int    i, sz;
  354.  
  355.     ENTERCRITICALSECTION(iCS);
  356.     v = iTab;
  357.     sz = iSize;
  358.     iSize = size;
  359.     iTab = Tncalloc(NODE, size);
  360.     iNelm = 0;
  361.     for (i=0 ; i != sz ; ++i)  {
  362.         NODE    n, t;
  363.  
  364.         for (n=v[i] ; n ; n = t)  {
  365.             Lookup(self, n->luk, HT_ADD, 0, LTYPE, NULL);
  366.             t = n->next;
  367.             free_node(n);
  368.         }
  369.     }
  370.     free(v);
  371.     LEAVECRITICALSECTION(iCS);
  372.     return self;
  373. }
  374.  
  375. static    unsigned    hash_string(char *s)
  376. {
  377.     register char     c = 'a';
  378.     double    t;
  379.     register unsigned short     k=0;  /* must be short     */
  380.  
  381.     while (*s)
  382.         k += *s++ ^ c++;
  383.     t = .6125423371    * k;
  384.     t = t < 0.0 ? -t : t;
  385.     return (int) (BIG_INT * (t - floor(t)));
  386. }
  387.  
  388. static    unsigned    hash_short(int val)
  389. {
  390.     double    t;
  391.  
  392.     t = .6125423371    * (unsigned) val;
  393.     t = t < 0.0 ? -t : t;
  394.     return (unsigned) (BIG_INT * (t - floor(t)));
  395. }
  396.  
  397. imeth    gLookup : Lookup (luk, int mode, int deep, int type, value)
  398.                 /*  0=Set, 1=Dictionary, 2=StringDictionary, 
  399.             3=ShortDictionary, 4=IntegerDictionary */
  400.                 /*  0=no, 1=1 level, 2=deep    */
  401. {
  402.     NODE    e, laste=NULL, newe;
  403.     unsigned     idx;
  404.     int    i=0;
  405.     struct _Object_iv_t * volatile ret;
  406.  
  407.     ENTERCRITICALSECTION(iCS);
  408.     if (type == 2)
  409.         idx = hash_string((char *) luk) % iSize;
  410.     else if (type == 3  ||  type == 4)
  411.         idx = hash_short(*((int *) luk)) % iSize;
  412.     else
  413.         idx = gHash(luk) % iSize;
  414.     if (idx >= (unsigned) iSize)
  415.         idx %= iSize;
  416.     e = iTab[idx];
  417.     while (1)  {
  418.         if (e == NULL)    {
  419.             if (mode != HT_ADD  &&  mode != HT_FINDADD) {
  420.                 LEAVECRITICALSECTION(iCS);
  421.                 return(NULL);
  422.             }
  423.             e = new_node();
  424.             switch (type)  {
  425.             case 0:
  426.             default:
  427.                 e->luk = luk;
  428.                 break;
  429.             case 1:
  430.                 e->luk = gNewWithObjObj(ObjectAssociation, luk, value);
  431.                 break;
  432.             case 2:
  433.                 e->luk = gNewWithStrObj(StringAssociation, (char *) luk, value);
  434.                 break;
  435. //            case 3:
  436. //                e->luk = gNewWithIntObj(ShortAssociation, *((int *)luk), value);
  437. //                break;
  438.             case 4:
  439.                 e->luk = gNewWithIntObj(IntegerAssociation, *((int *)luk), value);
  440.                 break;
  441.             }
  442.             e->next    = NULL;
  443.             if (laste)
  444.                 laste->next = e;
  445.             else
  446.                 iTab[idx] = e;
  447.             ++iNelm;
  448.             break;
  449.         }
  450.         switch (type)  {
  451.         case 0:
  452.             i = e->luk == luk ? 0 : gCompare(e->luk, luk);
  453.             break;
  454.         case 1:  {
  455.             object    t = gKey(e->luk);
  456.             i = t == luk ? 0 : gCompare(t, luk);
  457.             break;
  458.         }
  459.         case 2:  {
  460.             char    *t = gStringKey(e->luk);
  461.             i = t == (char *) luk ? 0 : strcmp(t, (char *) luk);
  462.             break;
  463.         }
  464. //        case 3:
  465. //            i = gShortKey(e->luk) - *((int *) luk);
  466. //            break;
  467.         case 4:
  468.             i = gIntKey(e->luk) - *((int *) luk);
  469.             break;
  470.         }
  471.         if (!i)  {
  472.             if (mode == HT_ADD) {
  473.                 LEAVECRITICALSECTION(iCS);
  474.                 return(NULL);
  475.             }
  476.             if (mode == HT_DELETE)  {
  477.                 if (deep == 1)
  478.                     gDispose(e->luk);
  479.                 else if (deep == 2)
  480.                     gDeepDispose(e->luk);
  481.                 if (laste)
  482.                     laste->next = e->next;
  483.                 else
  484.                     iTab[idx] = e->next;
  485.                 ret = e->luk;
  486.                 free_node(e);
  487.                 --iNelm;
  488.                 LEAVECRITICALSECTION(iCS);
  489.                 return deep ? self : (object) ret;
  490.             }  
  491.             break;
  492.         }  else if (i > 0)  {
  493.             if (mode != HT_ADD  &&  mode != HT_FINDADD) {
  494.                 LEAVECRITICALSECTION(iCS);
  495.                 return(NULL);
  496.             }
  497.             newe = new_node();
  498.             switch (type)  {
  499.             case 0:
  500.             default:
  501.                 newe->luk = luk;
  502.                 break;
  503.             case 1:
  504.                 newe->luk = gNewWithObjObj(ObjectAssociation, luk, value);
  505.                 break;
  506.             case 2:
  507.                 newe->luk = gNewWithStrObj(StringAssociation, (char *) luk, value);
  508.                 break;
  509. //            case 3:
  510. //                newe->luk = gNewWithIntObj(ShortAssociation, *((int *) luk), value);
  511. //                break;
  512.             case 4:
  513.                 newe->luk = gNewWithIntObj(IntegerAssociation, *((int *) luk), value);
  514.                 break;
  515.             }
  516.             newe->next = e;
  517.             if (laste)
  518.                 laste->next = newe;
  519.             else
  520.                 iTab[idx] = newe;
  521.             e = newe;
  522.             ++iNelm;
  523.             break;
  524.         }  else     {
  525.             laste =    e;
  526.             e = e->next;
  527.         }
  528.     }
  529.     ret = e->luk;
  530.     LEAVECRITICALSECTION(iCS);
  531.     return (object) ret;
  532. }
  533.  
  534. imeth    gSequence ()
  535. {
  536.     return gNewSetSeq(SetSequence, iSize, iNelm, (void *) iTab);
  537. }
  538.  
  539. static    void    class_init(void)
  540. {
  541.     INITIALIZECRITICALSECTION(cCS);
  542. }
  543.  
  544.  
  545. /*                                      
  546.  *
  547.  *      Copyright (c) 1993-1996 Algorithms Corporation
  548.  *      3020 Liberty Hills Drive
  549.  *      Franklin, TN 37067
  550.  *
  551.  *      ALL RIGHTS RESERVED.
  552.  *
  553.  *      
  554.  *      
  555.  */
  556.  
  557.  
  558.